/*
*       ID : pallab81
*       PROG : 11643_3
*       LANG : C++
*       2012-09-10-10.15.09 Monday
*
*       "I have not failed, I have just found 10000 ways that won't work.
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <fstream>
#include <string>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <bitset>
#include <iomanip>

#include <ctime>
#include <cassert>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <climits>
#include <cstring>
#include <cstdlib>

using namespace std;


#define foR(i1,st,ed) for(int i1 = st , j1 = ed ; i1 < j1 ; ++i1 )
#define fo(i1,ed) foR( i1 , 0 , ed )
#define foE(i1,st,ed) foR( i1, st, ed+1 )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )
#define line puts("")

template<class T1>
inline void debug(T1 _x) {
    cout<<_x<<'\n';
}
template<class T1, class T2>
inline void debug(T1 _x,T2 _y) {
    cout<<_x<<' '<<_y<<'\n';
}
template<class T1, class T2, class T3>
inline void debug(T1 _x,T2 _y,T3 _z) {
    cout<<_x<<' '<<_y<<' '<<_z<<'\n';
}
template<class T1, class T2, class T3, class T4>
inline void debug(T1 _x,T2 _y,T3 _z,T4 _zz) {
    cout<<_x<<' '<<_y<<' '<<_z<<' '<<_zz<<'\n';
}
template< class T1>
inline void debug(T1 _array,int _size) {
    cout<<"[";
    for (int i=0; i<_size; ++i) {
        cout<<' '<<_array[i];
    }
    puts(" ]");
}
inline bool CI(int &_x) {
    return scanf("%d",&_x)==1;
}
inline bool CI(int &_x, int &_y) {
    return CI(_x)&&CI(_y) ;
}
inline bool CI(int &_x, int &_y, int &_z) {
    return CI(_x)&&CI(_y)&&CI(_z) ;
}
inline bool CI(int &_x, int &_y, int &_z, int &_zz) {
    return CI(_x)&&CI(_y)&&CI(_z)&&CI(_zz) ;
}
inline void wait( double seconds ) {
    double endtime = clock()+( seconds* CLOCKS_PER_SEC );
    while( clock() < endtime ) {
        ;
    }
}
#if !defined( ONLINE_JUDGE )
#define debug
#endif
template<class T1, class T2>
inline T1 OR(T1 msk,T2 bit) {
    return ( msk|(1<<bit) );
}
template<class T1, class T2>
inline T1 AND(T1 msk, T2 bit) {
    return ( msk&(1<<bit) );
}
template<class T1, class T2>
inline T1 Clear(T1 msk, T2 bit) {
    return ( msk&(~(1<<bit)));
}
template<class T1, class T2>
inline bool marked(T1 msk, T2 bit) {
    return ( AND(msk,bit)!=0 );
}
struct NODE {
    int R;
    int C;
    NODE(int R=0,int C=0):
        R(R),C(C) {
        ;
    }
};
NODE interesting[16];
int grid_size, interesting_count;

inline void read() {
    CI(grid_size, interesting_count);
    fo(i, interesting_count) {
        CI( interesting[i].R, interesting[i].C);
        //interesting[i].R-=1;
        //interesting[i].C-=1;
    }
}
int dist[16][16];
const int inf = 1023456789;
inline int case1(int r1, int c1, int r2, int c2) {
    if(r1==1&&c1==1&&r2==2&&c2==2)return 4;
    if(r2==1&&c2==1&&r1==2&&c1==2)return 4;
    return 0;
}
inline int case2(int r1, int c1, int r2, int c2) {
    if(r1==grid_size&&c1==grid_size&&r2==grid_size-1&&c2==grid_size-1)return 4;
    if(r2==grid_size&&c2==grid_size&&r1==grid_size-1&&c1==grid_size-1)return 4;
    return 0;
}
inline int case3(int r1, int c1, int r2, int c2) {
    if(r1==grid_size&&c1==1&&r2==grid_size-1&&c2==2)return 4;
    if(r2==grid_size&&c2==1&&r1==grid_size-1&&c1==2)return 4;
    return 0;
}
inline int case4(int r1, int c1, int r2, int c2) {
    if(r1==1&&c1==grid_size&&r2==2&&c2==grid_size-1)return 4;
    if(r2==1&&c2==grid_size&&r1==2&&c1==grid_size-1)return 4;
    return 0;
}

inline int fun(int i, int j) {
    int r1 = interesting[i].R;
    int r2 = interesting[j].R;
    int c1 = interesting[i].C;
    int c2 = interesting[j].C;
    int ar[4] = { case1(r1,c1,r2,c2), case2(r1,c1,r2,c2),case3(r1,c1,r2,c2),case4(r1,c1,r2,c2) };
    fo(i,4) {
        if(ar[i])return ar[i];
    }

    int a = abs(r2-r1);
    int b = abs(c2-c1);
    if(a<b)swap(a,b);
    if(a==1&&b==0)return 3;
    if(a==2&&b==2)return 4;
    int ans = max( (a+1)/2, (a+b+2)/3 );
    if( (ans%2) != (a+b)%2 )ans++;
    return ans;
}
inline void calc_dist() {
    fo(i,16) {
        fill( dist[i], dist[i]+16, inf);
    }
    fo(i,interesting_count) {
        fo(j,interesting_count) {
            if(i==j) {
                dist[i][j]=0;
            } else {
                dist[i][j] = fun( i,j) ;
            }
        }
    }
}
int K;
bool vis[1<<16][16];
int dp[1<<16][16];
int go(int msk,int p, int s) {
    if( msk==0 ) {
        return dist[p][s];
    }
    if(vis[msk][p])return dp[msk][p];
    vis[msk][p]=true;
    int bst=inf;
    fo(i,interesting_count) {
        if( marked(msk,i) ) {
            int v = go( Clear(msk,i) , i, s )+dist[p][i];
            bst=min(bst,v);
        }
    }
    dp[msk][p]=bst;
    return bst;
}
inline void proc() {
    calc_dist();


    SET(vis,false);
    int bst=go( Clear( (1<<interesting_count)-1 ,0), 0,0 ) ;
    cout<<bst;
    line;
    ++K;
}
int main() {
    int kase=1;
#if !defined ( ONLINE_JUDGE )
    freopen("in","r",stdin);
#endif

    scanf("%d",&kase);
    foE(i,1,kase) {
        read();
        cout<<"Case "<<i<<": ";
        proc();
    }
    return 0;
}
